#-*- coding: utf-8 -*-

# # 问题描述：
# 给定一个字符串，找出不含有重复字符的最长子串的长度

# 示例 1:
# 输入: "abcabcbb"
# 输出: 3 
# 解释: 无重复字符的最长子串是 "abc"，其长度为 3

# 示例 2:
# 输入: "bbbbb"
# 输出: 1
# 解释: 无重复字符的最长子串是 "b"，其长度为 1
# 示例 3:

# 输入: "pwwkew"
# 输出: 3
# 解释: 无重复字符的最长子串是 "wke"，其长度为 3
# 请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串

# # 解决方案1：
# # 尝试使用哈希表来获取字符串中不重复的字符的数目，错误的忽略掉问题中最长字串的条件
# # 尝试在出现重复时，清除哈希重新开始计算，以求得最长字串，但是思路错误，比如"dvdf"
# # 错误的思路
# class Solution(object):
#     def lengthOfLongestSubstring(self, s):
#         """
#         :type s: str
#         :rtype: int
#         """
#         length_max = 0;
#         dic = {};
#         for index in xrange(len(s)):
#             if dic.has_key(s[index]):
#                 if len(dic.keys()) > length_max:
#                     length_max = len(dic.keys());
#                     dic.clear();
#             dic.setdefault(s[index], 1);
#         if len(dic.keys()) > length_max:
#             length_max = len(dic.keys());
#         return length_max;

# 暴力破解方案
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length_max = 0;
        dic = {};
        for i in xrange(len(s)):
            for j in xrange(i, len(s)):
                if dic.has_key(s[j]):
                    if len(dic.keys()) > length_max:
                        length_max = len(dic.keys());
                    dic.clear();
                    break;
                dic.setdefault(s[j], 1);
            i = i + 1;
        if len(dic.keys()) > length_max:
            length_max = len(dic.keys());
        return length_max;

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0;
        char_map = {};
        i = -1;
        for j in xrange(0, len(s)):
            if char_map.has_key(s[j]):
                i = max(i, char_map[s[j]]);
            max_length = max(max_length, j - i);
            char_map[s[j]] = j;
        return max_length;


t = Solution();
print t.lengthOfLongestSubstring("abcabcbb");

# # 阅读官方提供的答案
# # 解决方案1：滑动窗口算法
# # 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引j，如果它不在HashSet中，我们会继续滑动j。直到s[j]已经存在于HashSet中。此时，我们找到的没有重复字符的最长子字符串将会以索引i开头
# public class Solution {
#     public int lengthOfLongestSubstring(String s) {
#         int n = s.length();
#         Set<Character> set = new HashSet<>();
#         int ans = 0, i = 0, j = 0;
#         while (i < n && j < n) {
#             // try to extend the range [i, j]
#             if (!set.contains(s.charAt(j))){
#                 set.add(s.charAt(j++));
#                 ans = Math.max(ans, j - i);
#             }
#             else {
#                 set.remove(s.charAt(i++));
#             }
#         }
#         return ans;
#     }
# }

# # 解决方案2：优化滑动窗口算法
# # 相对于解决方案1，优化的地方在于节省点发生重复时查找i的时间
# public class Solution {
#     public int lengthOfLongestSubstring(String s) {
#         int n = s.length(), ans = 0;
#         Map<Character, Integer> map = new HashMap<>(); // current index of character
#         // try to extend the range [i, j]
#         for (int j = 0, i = 0; j < n; j++) {
#             if (map.containsKey(s.charAt(j))) {
#                 i = Math.max(map.get(s.charAt(j)), i);
#             }
#             ans = Math.max(ans, j - i + 1);
#             map.put(s.charAt(j), j + 1);
#         }
#         return ans;
#     }
# }

# # 解决方案3：
# # 相对于解决方案2，使用数组代替了哈希
# public class Solution {
#     public int lengthOfLongestSubstring(String s) {
#         int n = s.length(), ans = 0;
#         int[] index = new int[128]; // current index of character
#         // try to extend the range [i, j]
#         for (int j = 0, i = 0; j < n; j++) {
#             i = Math.max(index[s.charAt(j)], i);
#             ans = Math.max(ans, j - i + 1);
#             index[s.charAt(j)] = j + 1;
#         }
#         return ans;
#     }
# }

# # 学习到的内容：
# # 滑动窗口求取最大不重复子字符串